package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.ListNode;

import java.util.Locale;
import java.util.Stack;

/**
 * 从尾到头打印链表
 *
 * @author yuhushuan
 * @date 2020/5/30 22:47
 */
public class _06_1_PrintListInReversedOrder {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 10; i++) {
            ListNode next = new ListNode(i);
            node.setNext(next);
            node = next;
        }
        print(head);
    }

    private static void print(ListNode head) {
        System.out.println(String.format(Locale.getDefault(),
                "链表遍历：\n%s", head));
        System.out.println("反向链表-栈实现打印：");
        printListReversibly_Iteratively(head);

        System.out.println("反向链表-递归实现打印：");
        printListReversibly_Recursively(head);
        System.out.println();

        System.out.println("反向链表-移动指针实现：");
        System.out.println(listReversibly(head));
    }

    /**
     * 利用栈
     *
     * @param head
     */
    private static void printListReversibly_Iteratively(ListNode head) {
        Stack<ListNode> nodes = new Stack<>();
        ListNode node = head;
        while (node != null) {
            nodes.push(node);
            node = node.getNext();
        }

        while (!nodes.empty()) {
            node = nodes.pop();
            System.out.print(node.getValue());
            if (!nodes.empty()) {
                System.out.print(", ");
            }
        }
        System.out.println();
    }

    /**
     * 递归，链表非常长时会导致调用栈溢出
     *
     * @param head
     */
    private static void printListReversibly_Recursively(ListNode head) {
        if (head != null) {
            if (head.getNext() != null) {
                printListReversibly_Recursively(head.getNext());
            }
            System.out.print(head.getValue());
            System.out.print(", ");
        }
    }

    /**
     * 修改为反向链表，移动指针方式
     *
     * @param head
     */
    private static ListNode listReversibly(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode last = head;

        while (last.getNext() != null) {
            ListNode nextNode = last.getNext();
            last.setNext(nextNode.getNext());
            nextNode.setNext(head);
            head = nextNode;
        }
        return head;
    }
}
